class RecentCounter {
public:
    queue<int>st;
    RecentCounter() {

    }

    int ping(int t) {
        st.push(t);
        while (st.front() < t - 3000)
            st.pop();
        int ret = st.size();
        return  ret;



    }
};

/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter* obj = new RecentCounter();
 * int param_1 = obj->ping(t);
 */class Solution {
 public:
     int compareVersion(string version1, string version2) {
         int m = version1.size();
         int n = version2.size();
         int cur1 = 0, cur2 = 0;

         while (cur1 < m || cur2 < n)
         {
             long long a = 0; long long b = 0;
             while (cur1 < m && version1[cur1] != '.')
             {
                 a = a * 10 + version1[cur1++] - '0';
             }
             cur1++;

             while (cur2 < n&& version2[cur2] != '.')
             {
                 b = b * 10 + version2[cur2++] - '0';
             }
             cur2++;




             if (a != b) return a > b ? 1 : -1;



         }
         return 0;
     }
 };/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 class Solution {
 public:
     ListNode* rotateRight(ListNode* head, int k) {
         if (head == nullptr)return nullptr;
         int n = 1;
         ListNode* cur = head;
         while (cur->next)cur = cur->next, n++;
         cur->next = head;
         for (int i = 0; i < n - k % n; i++)
         {
             cur = cur->next;


         }
         head = cur->next;
         cur->next = nullptr;

         return head;


     }
 };/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 class Solution {
 public:
     ListNode* reverseBetween(ListNode* head, int left, int right) {
         ListNode* pro = new  ListNode(0);
         pro->next = head;
         ListNode* pre = pro;
         for (int i = 0; i < left - 1; i++)
         {
             pre = pre->next;
         }
         ListNode* cur = pre->next;
         for (int i = 0; i < right - left; i++)
         {
             ListNode* next = cur->next;
             cur->next = next->next;
             next->next = pre->next;
             pre->next = next;
         }
         return pro->next;



     }
 };/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 class Solution {
 public:
     ListNode* reverseBetween(ListNode* head, int left, int right) {
         ListNode* pro = new  ListNode(0);
         pro->next = head;
         ListNode* pre = pro;
         for (int i = 0; i < left - 1; i++)
         {
             pre = pre->next;
         }
         ListNode* cur = pre->next;
         for (int i = 0; i < right - left; i++)
         {
             ListNode* next = cur->next;
             cur->next = next->next;
             next->next = pre->next;
             pre->next = next;
         }
         return pro->next;



     }
 }; class Solution {
 public:
     bool used[210];
     int n;
     int findCircleNum(vector<vector<int>>& isConnected) {
         n = isConnected.size();
         int ret = 0;
         for (int i = 0; i < n; i++)
         {
             if (!used[i])
             {
                 ret++;
                 dfs(isConnected, i);


             }





         }
         return ret;


     }
     void dfs(vector<vector<int>>& isConnected, int pos)
     {
         used[pos] = true;
         for (int i = 0; i < n; i++)
         {
             if (!used[i] && isConnected[pos][i])
             {


                 dfs(isConnected, i);


             }



         }







     }
 }; class Solution {
 public:

     bool rotateString(string s, string goal) {

         if (s.size() != goal.size())

             return false;



         s += s;

         int m = s.size();
         int k = goal.size();
         //cout<<s;
         for (int i = 0; i < m - k; i++)
         {
             string str = s.substr(i, k);
             cout << str << endl;
             if (strcmp(str.c_str(), goal.c_str()) == 0)
                 return true;




         }

         return  false;

     }
 };/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 class Solution {
 public:
     void deleteNode(ListNode* node) {
         node->val = node->next->val;
         node->next = node->next->next;
     }
 };/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 class Solution {
 public:
     ListNode* partition(ListNode* head, int x) {
         ListNode* less = new  ListNode(-1);
         ListNode* more = new  ListNode(-1);
         ListNode* cur = head;
         ListNode* curless = less;
         ListNode* curmore = more;

         while (cur)
         {
             if (cur->val < x)
             {
                 ListNode* newnode = new  ListNode(cur->val);
                 curless->next = newnode;
                 curless = curless->next;
             }
             else
             {
                 ListNode* newnode = new  ListNode(cur->val);
                 curmore->next = newnode;
                 curmore = curmore->next;



             }
             cur = cur->next;
         }
         curless->next = more->next;
         return less->next;







     }
 }; class Solution {
 public:
     bool isPowerOfTwo(int n) {
         return n > 0 && (n & n - 1) == 0;
     }
 };